{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How to solve the coin [balance puzzle](https://en.wikipedia.org/wiki/Balance_puzzle#Twelve-coin_problem) programmatically.\n",
    "\n",
    "Given a balance and a set of coins, which are all equal in weight except for one, determine which coin is of different weight in as few weighings as possible.\n",
    "\n",
    ">Twelve-coin problem\n",
    "\n",
    ">A more complex version has twelve coins, eleven or twelve of which are identical. If one is different, we don't know whether it is heavier or lighter than the others. This time the balance may be used three times to determine if there is a unique coin—and if there is, to isolate it and determine its weight relative to the others. (This puzzle and its solution first appeared in an article in 1945.[2]) The problem has a simpler variant with three coins in two weighings, and a more complex variant with 39 coins in four weighings.\n",
    "\n",
    "First to model the data:\n",
    "* An `enum` to represent different weights.  Following the ternary comparison convention, such as Python 2's [cmp](https://docs.python.org/2.7/library/functions.html?highlight=cmp#cmp), is convenient.\n",
    "* An object to represent the balance.  For testing, it will need to be configurable with the target coin and relative weight.\n",
    "* An object to represent a coin and its state.  A `class` is tempting, but the most useful data structure would keep the coins grouped by their known (or unknown) state anyway.  So any hashable unique identifier is sufficient."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import enum\n",
    "\n",
    "class Weight(enum.IntEnum):\n",
    "    LIGHT = -1\n",
    "    EVEN = 0\n",
    "    HEAVY = 1\n",
    "\n",
    "class Balance:\n",
    "    def __init__(self, coin, weight: Weight):\n",
    "        self.coin = coin\n",
    "        self.weight = weight\n",
    "\n",
    "    def weigh(self, left: set, right: set):\n",
    "        \"\"\"Return relative Weight of left side to right side.\"\"\"\n",
    "        assert len(left) == len(right)\n",
    "        if self.coin in left:\n",
    "            return self.weight\n",
    "        if self.coin in right:\n",
    "            return Weight(-self.weight)\n",
    "        return Weight.EVEN\n",
    "\n",
    "coins = 'abcdefghijkl'\n",
    "assert len(coins) == 12\n",
    "balance = Balance('a', Weight.LIGHT)\n",
    "assert balance.weigh('a', 'b') == Weight.LIGHT\n",
    "assert balance.weigh('b', 'c') == Weight.EVEN\n",
    "assert balance.weigh('b', 'a') == Weight.HEAVY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As is typical with [induction puzzles](https://en.wikipedia.org/wiki/Induction_puzzles), the constants chosen are just large enough to thwart an iterative approach.  The 2 weighing variation would be trivial enough for most people to brute force the solution.  Whereas 4 weighings would already be such a large decision tree, it would be tedious to even output.  The easier approach is solve the puzzle recursively and more generally, for any number of coins and weighings.\n",
    "\n",
    "So what can be done in a single weighing?  Clearly all weighings must have an equal number of coins on each side, else nothing is learned.  If it balances, then the different coin is in the unweighed group.  If it doesn't balance, then the different coin is in the weighed group, but additionally it is known whether each coin would be heavy or light based on which side it was on.  This is the crucial insight: there's a variant recursive puzzle embedded inside this puzzle.\n",
    "\n",
    "The [Towers of Hanoi](https://en.wikipedia.org/wiki/Tower_of_Hanoi) is a classic puzzle often used in computer science curricula to teach recursion.  This one would suitable as a subsequent more advanced problem.\n",
    "\n",
    "So what can be done with known coins in a single weighing?  If it balances, then as before the different coin is in the unweighed group.  But if it doesn't balance, then which way can be used to further narrow the coins.  Consider the heavier side; the different coin must be one of the heavy ones on that side, or one of the light ones on the other side.  Therefore the coins can be split into 2 equal sized groups by putting equal numbers of heavy coins on each side, and equal numbers of light coins on each side.  One obstacle is that if there aren't an even number, there will need to be filler coins just to balance.  But that won't be a problem after the first weighing.\n",
    "\n",
    "Now we can implement a solution to the sub-problem, and build the need for filler coins into the balance implementation.  A generator is used so that the output of each weighing can be displayed. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "cba dfe\na e\na \n"
    }
   ],
   "source": [
    "import itertools\n",
    "\n",
    "class Balance:\n",
    "    def __init__(self, coin, weight: Weight):\n",
    "        self.coin = coin\n",
    "        self.weight = weight\n",
    "        self.filler = set()\n",
    "\n",
    "    def weigh(self, left: set, right: set):\n",
    "        \"\"\"Return relative Weight of left side to right side.\"\"\"\n",
    "        assert abs(len(left) - len(right)) <= len(self.filler)\n",
    "        if self.coin in left:\n",
    "            return self.weight\n",
    "        if self.coin in right:\n",
    "            return Weight(-self.weight)\n",
    "        return Weight.EVEN\n",
    "\n",
    "    def find(self, light: set, heavy: set):\n",
    "        \"\"\"Recursively find target coin from sets of potentially light and heavy coins.\"\"\"\n",
    "        yield light, heavy\n",
    "        union = light | heavy\n",
    "        if len(union) <= 1:\n",
    "            return\n",
    "        left, right = set(), set()\n",
    "        # split into 3 groups\n",
    "        for start, third in enumerate([left, right]):\n",
    "            for group in (light, heavy):\n",
    "                third.update(itertools.islice(group, start, None, 3))\n",
    "        weight = self.weigh(left, right)\n",
    "        if weight < 0:\n",
    "            light, heavy = (light & left), (heavy & right)\n",
    "        elif weight > 0:\n",
    "            light, heavy = (light & right), (heavy & left)\n",
    "        else:\n",
    "            light, heavy = (light - left - right), (heavy - left - right)\n",
    "        self.filler.update(union - light - heavy)\n",
    "        yield from self.find(light, heavy)\n",
    "\n",
    "balance = Balance('a', Weight.LIGHT)\n",
    "for light, heavy in balance.find(set('abc'), set('def')):\n",
    "    print(''.join(light), ''.join(heavy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now with the sub-problem solved, there's just one thing missing for the main puzzle.  In the known case, splitting into 3 equal sized groups is cleary optimal.  But in the unknown case, we need to know how many coins to exclude from the weighing.  This requires computing how many coins can be handled in the subsolution.  Lucikly it's a trivial [recurrence relation](https://en.wikipedia.org/wiki/Recurrence_relation): `n` weighings can solve 3 times the number of `n - 1` weighings.\n",
    "$$\n",
    "\\prod_{}^n 3 = 3^n\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "dbah fceg\na e\na \n"
    }
   ],
   "source": [
    "class Balance(Balance):\n",
    "    def solve(self, count: int, coins):\n",
    "        \"\"\"Recursively find target coin.\"\"\"\n",
    "        if count <= 0:\n",
    "            return\n",
    "        weigh = set(itertools.islice(coins, 3 ** (count - 1) - (not self.filler)))\n",
    "        exclude = set(coins) - weigh\n",
    "        left, right = (set(itertools.islice(weigh, start, None, 2)) for start in range(2))\n",
    "        weight = self.weigh(left, right)\n",
    "        self.filler.update(exclude if weight else weigh)\n",
    "        if weight < 0:\n",
    "            yield from self.find(left, right)\n",
    "        elif weight > 0:\n",
    "            yield from self.find(right, left)\n",
    "        else:\n",
    "            yield from self.solve(count - 1, exclude)\n",
    "\n",
    "balance = Balance('a', Weight.LIGHT)\n",
    "for light, heavy in balance.solve(3, coins):\n",
    "    print(''.join(light), ''.join(heavy))\n",
    "\n",
    "for coin in coins:\n",
    "    light, heavy =  list(Balance(coin, Weight.LIGHT).solve(3, coins))[-1]\n",
    "    assert light == {coin} and not heavy\n",
    "    light, heavy =  list(Balance(coin, Weight.HEAVY).solve(3, coins))[-1]\n",
    "    assert not light and heavy == {coin}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The puzzle is solved.  There's one last simplifcation that can be made, but requires a bit more math background.  Ideally we wouldn't need to know the objective number of weighings; the algorithm would just solve any set of coins as efficiently as possible.  To do that, the number of coins that can be solved has to be computed.  As was done above, but this recurrence relation is more advanced: each weighing can solve `3 ^ n` more coins.\n",
    "$$\n",
    "\\sum_{k=0}^{n-1} 3^k = (3^n - 1) / 2\n",
    "$$\n",
    "\n",
    "With that calculation inverted, the `count` can be removed from the interface"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "dbah fceg\na e\na \n"
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "class Balance(Balance):\n",
    "    def solve(self, coins):\n",
    "        if not coins:\n",
    "            return\n",
    "        count = math.ceil(math.log(len(coins) * 2 + 1, 3))\n",
    "        weigh = set(itertools.islice(coins, 3 ** (count - 1) - (not self.filler)))\n",
    "        exclude = set(coins) - weigh\n",
    "        left, right = (set(itertools.islice(weigh, start, None, 2)) for start in range(2))\n",
    "        weight = self.weigh(left, right)\n",
    "        self.filler.update(exclude if weight else weigh)\n",
    "        if weight < 0:\n",
    "            yield from self.find(left, right)\n",
    "        elif weight > 0:\n",
    "            yield from self.find(right, left)\n",
    "        else:\n",
    "            yield from self.solve(exclude)\n",
    "\n",
    "balance = Balance('a', Weight.LIGHT)\n",
    "for light, heavy in balance.solve(coins):\n",
    "    print(''.join(light), ''.join(heavy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice the formula indicates it's possible to do 13 coins in 3 weighings, and it would be with a filler coin to balance out the 9 that need weighing."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.2 64-bit",
   "env": {},
   "interrupt_mode": "signal",
   "language": "python",
   "metadata": {},
   "name": "python38264bit6228900fdf124674a4003cd0eb83b67d"
  },
  "nikola": {
   "category": "puzzles",
   "date": "2020-06-07",
   "description": "",
   "link": "",
   "slug": "coin-balance",
   "tags": "",
   "title": "Coin balance",
   "type": "text"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}